#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct BiTree
{
    ElemType data;
    struct BiTree *lchild;
    struct BiTree *rchild;
}BiTree,*Tree;
typedef struct
{
    ElemType *elem;
    int Tablelen;
}SStable;

int Bst_insert(Tree &T,ElemType k)
{
    if (T==NULL)
    {
        T=(Tree) calloc(1,sizeof(BiTree));
        T->data=k;
        return 1;
    }
    else if (T->data==k)
    {
        return 0;
    }
    else if(k>T->data)
    {
        return Bst_insert(T->rchild,k);
    }
    else
    {
        return Bst_insert(T->lchild,k);
    }

}
void Creat_Binary(Tree &T,ElemType *str,int n)
{
    int i=0;
    while(i<n){
        Bst_insert(T,str[i]);
        i++;
    }
}
void Inorder(Tree T,ElemType *str,int &pos)
{
    if (T!=NULL) {
        Inorder(T->lchild,str,pos);
        printf("%3d", T->data);
        str[pos++]=T->data;
        Inorder(T->rchild,str,pos);
    }
}
int BinarySearch(SStable ST,ElemType key)
{
   int low=0;
   int high=ST.Tablelen-1;
   int mid;
   while(low<=high)
   {
       mid=(low+high)/2;
       if (key>ST.elem[mid])
       {
            low=mid+1;
       }
       else if (key<ST.elem[mid])
       {
           high=mid-1;
       }
       else
       {
           return mid;
       }
   }
    return -1;
}
int main()
{
    Tree T=NULL;
    ElemType str[10];
    int pos=0,m;
    for (int i = 0; i < 10;i++) {
        scanf("%d",&str[i]);
    }
    Creat_Binary(T,str,10);
    Inorder(T,str,pos);
    printf("\n");
    SStable ST;
    ST.elem=str;//让顺序表指针指向数组
    ST.Tablelen=10;
    pos=BinarySearch(ST,21);
    printf("pos is %d\n",pos);
    return 0;
}